package org.example.struct.array2;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author liyishan
 * @date 2023/10/8 09:51
 * @apiNote
 */

public class Test00229MajorityElement {

    public static void main(String[] args) {
        int[] nums = {3,2,3};
        List<Integer> result = test(nums);
        System.out.println(JSON.toJSON(result));
    }

    public static List<Integer> test(int[] nums) {
        List<Integer> result = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        int count = 0;
        for(int i = 0; i < n; i++){
            count++;
            if(i+1 == nums.length || nums[i] != nums[i+1]){
                if(count > n/3){
                    result.add(nums[i]);
                }
                count = 0;
            }
        }
        return result;
    }

    public static List<Integer> test1(int[] nums){
        HashMap<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (cnt.containsKey(nums[i])) {
                cnt.put(nums[i], cnt.get(nums[i]) + 1);
            } else {
                cnt.put(nums[i], 1);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int x : cnt.keySet()) {
            if (cnt.get(x) > nums.length / 3) {
                ans.add(x);
            }
        }
        return ans;
    }

}
